package sliding_window

import (
	"math"
	"sort"
)

/*
209.给定一个含有n个【正整数】的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组[4,3]是该条件下的长度最小的子数组。

示例 2：
输入：target = 4, nums = [1,4,4]
输出：1

示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
明出处。
*/

//为了降低时间复杂度，可以使用滑动窗口的方法 滑动窗口
//时间复杂度：O(n)，其中 n 是数组的长度。指针 start 和 end 最多各移动 n 次。
//空间复杂度：O(1)。
func minSubArrayLen(target int, nums []int) int {
	left, right, s := 0, 0, 0

	//参数判断
	if len(nums) == 0 {
		return 0
	}

	ans := math.MaxInt32

	//扩大窗口
	for right < len(nums) {
		//移入数据，计算累加和
		s += nums[right]
		//收缩窗口：和>=target
		for s >= target {
			//最小长度
			ans = min(ans, right-left+1)
			//移出数据更新累加和
			s = s - nums[left]
			left++
		}
		right++

	}

	if ans == math.MaxInt32 {
		ans = 0
	}
	return ans
}

//暴力解法
//时间复杂度：O(n^2) 其中 n 是数组的长度。需要遍历每个下标作为子数组的开始下标，对于每个开始下标，需要遍历其后面的下标得到长度最小的子数组
//空间复杂度：O(1)
func minSubArrayLenB(s int, nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}
	ans := math.MaxInt32
	for i := 0; i < n; i++ {
		sum := 0
		for j := i; j < n; j++ {
			sum += nums[j]
			if sum >= s {
				ans = min(ans, j-i+1)
				break
			}
		}
	}

	if ans == math.MaxInt32 {
		return 0
	}
	return ans
}

//前缀和 + 二分查找
//在确定每个子数组的开始下标后，找到长度最小的子数组需要 O(n) 的时间。如果使用二分查找，则可以将时间优化到 O(logn)

//因为这道题保证了数组中每个元素都为正，所以前缀和一定是递增的，这一点保证了二分的正确性。如果题目没有说明数组中每个元素都为正，这里就不能使用二分来查找这个位置了
//时间复杂度：O(nlogn)，其中 n 是数组的长度。需要遍历每个下标作为子数组的开始下标，遍历的时间复杂度是 O(n)，
//为了使用二分查找，需要额外创建一个数组 sums 用于存储数组 \nums 的前缀和，其中 sums[i] 表示从 nums[0] 到 nums[i−1] 的元素和。
//得到前缀和之后，对于每个开始下标 i，可通过二分查找得到【大于或等于 i】 的最小下标 bound，使得 sums[bound]−sums[i−1]≥s，并更新子数组的最小长度（此时子数组的长度是bound−(i−1)）
//对于每个开始下标，需要通过二分查找得到长度最小的子数组，二分查找得时间复杂度是 O(logn)，因此总时间复杂度是 O(nlogn)。
//空间复杂度：O(n)，其中 n 是数组的长度。额外创建数组 sums 存储前缀和
func minSubArrayLenC(s int, nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}
	ans := math.MaxInt32
	sums := make([]int, n+1)
	//为了方便计算，领size=n+1
	//sums[0]=0 意味着前0个元素的前缀和为0
	//sums[1]=A[0] 前1个元素的前缀和为A[0],以此类推
	for i := 1; i <= n; i++ {
		sums[i] = sums[i-1] + nums[i-1]
	}

	for i := 1; i <= n; i++ {
		target := s + sums[i-1]
		bound := sort.SearchInts(sums, target)
		if bound < 0 {
			bound = -bound - 1
		}
		if bound <= n {
			ans = min(ans, bound-(i-1))
		}
	}

	if ans == math.MaxInt32 {
		return 0
	}
	return ans
}

/*
The result is initialized as res = n + 1.
One pass, remove the value from sum s by doing s -= A[j].
If s <= 0, it means the total sum of A[i] + ... + A[j] >= sum that we want.
Then we update the res = min(res, j - i + 1)
Finally we return the result res
*/
func minSubArrayLenSuper(target int, nums []int) int {
	i, n := 0, len(nums)
	res := n + 1 // initial

	for j := 0; j < n; j++ {
		target -= nums[j] // remove the value from sum
		for target <= 0 {
			res = min(res, j-i+1)
			target += nums[i]
			i++
		}
	}
	return res % (n + 1)
}
